package com.dbh.alg.datastructure;

/**
 * 合并 K 个升序链表
 * @author 董帮辉
 * @date 2025/5/10
 **/
public class E07Leetcode23 {

    /**
     * 合并两个有序链表-递归方式
     * @param p1 链表1
     * @param p2 链表2
     * @return 合并后的链表
     */
    public static ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        if (p1 == null) {
            return p2;
        }
        if (p2 == null) {
            return p1;
        }
        if (p1.val < p2.val) {
            p1.next = mergeTwoLists(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeTwoLists(p1, p2.next);
            return p2;
        }
    }

    /**
     * 合并k个有序链表
     * @param lists k个有序列表
     * @return 有序链表
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return split(lists, 0, lists.length-1);
    }

    /**
     * 将k个有序链表进行划分一个个链表进行合并
     * @param lists k个有序列表
     * @param i 左边界
     * @param j 有边界
     * @return 有序链表
     */
    public static ListNode split(ListNode[] lists, int i, int j) {
        if (i == j) {
            return lists[i];
        }
        int m = (i + j) >>> 1;
        ListNode left = split(lists, i, m);
        ListNode right = split(lists, m + 1, j);
        return mergeTwoLists(left, right);
    }

    public static void main(String[] args) {
        ListNode p1 = ListNode.of(1, 2, 2, 3);
        ListNode p2 = ListNode.of(2, 4, 5, 6);
        ListNode p3 = ListNode.of(1, 6, 7);
        ListNode p4 = ListNode.of(4, 9, 12);
        ListNode[] lists = {p1, p2, p3, p4};
        System.out.println(mergeKLists(lists));
    }

}
